Písemka 20.1.2006

Byla v poho..
1:
a) Co je usporádání na mnozine, a zda je usp.:
i) X={1..100} x(R1)y <=> x-y<10
ii) X={1..100} x(R2)y <=> x/y<=10
iii) X je mnozina zobrazení z {a,b,c,d,e} do {1,2,3}
f(R3)g <=> f(a)>=g(a), f(c)>=g(c), f(e)>=g(e)
HINT: Ani jedno nejni usporádání.

b) Binomiální veta, a pomocí: (sqrt(14^13)-1)(sqrt(14^13)+1) je delitelne 169
HINT: roznasob zavorky, dostanes 14^13-1, a to uz jsme resily v jiném fóru.

c) Definice stromu, nakreslyt vsechny neizomorfní stromi na secti vrcholech.

2: Euleruv vzorec (|V|-|E|-s=2)
Napsat a dokázat.

3: (3,3...3,4,4...4) n trojek a n ctirek, na jake n bude skóre grafu.

4: Jestly muze mit stejne skore:
no...ale ze co tam bylo, ta nevim...stromy, souvisly a 2-souvisly grafy a na konce jeden, ze strom a nerovinny graf. Bylo celkem 7 páru.

Hodne stesti

... ted jsi me dostal. Ja mel pocit ze tam je def. izomorfismu.

1. c) "Napiste definici izomorfismu grafu. Nakreslete vsechny neizomorfni stromy se sesti vrcholy. (Zduvodnete.)"

2. "Mohou mit dva grafy G1 a G2 stejne skore, jestlize

(a) G1 je souvisily, G2 neni souvisly,
(b) G1 je 2-souvisly, G2 neni souvisly,
(c) G1 je 2-souvisly, zadna komponenta G2 neni 2-souvisla,
(d) G1 je strom, G2 neni souvisly,
(e) G1 je strom, G2 je 2-souvisly,
(f) G1 neni rovinny, G2 je kruznice,
(g) G1 neni rovinny, G2 je strom?"

Hint (BEZ ZARUKY!): a) ano, b) ano, c) ne?, d) ne?, e) ne, f) ne, g) ne?

Anonymous wrote:1. c) "Napiste definici izomorfismu grafu. Nakreslete vsechny neizomorfni stromy se sesti vrcholy. (Zduvodnete.)"

4. "Mohou mit dva grafy G1 a G2 stejne skore, jestlize

(a) G1 je souvisily, G2 neni souvisly,
(b) G1 je 2-souvisly, G2 neni souvisly,
(c) G1 je 2-souvisly, zadna komponenta G2 neni 2-souvisla,
(d) G1 je strom, G2 neni souvisly,
(e) G1 je strom, G2 je 2-souvisly,
(f) G1 neni rovinny, G2 je kruznice,
(g) G1 neni rovinny, G2 je strom?"

Hint (BEZ ZARUKY!): a) ano, b) ano, c) ne?, d) ne?, e) ne, f) ne, g) ne?

c) ano
d) ano - G1: cesta z peti vrcholu (1,2,2,2,1) G2: trojuhelnik a dva spojeny body
g) ano - napr. G2: v koreni vetveni na 4 vetve - v tech 4 bodech dalsi vetveni do 3 => 5xvrchol stupne 4 a 12 listu ... G1: K5 a 6 "usecek"

Skvela pisemka, jeste aby tak dopadly principy... :)

Myshaak wrote:... ted jsi me dostal. Ja mel pocit ze tam je def. izomorfismu.

Sorry, mas pravdu..ja to popletl.

(c) G1 je 2-souvisly, zadna komponenta G2 neni 2-souvisla,

HINT:

G2:
   o---o---o---o     {  o je vrchol, hrany jsou --- nebo \ nebo /  }
    \o/     \o/
G1: cyklus delky 6 + jedna hrana.

Ja mel za 1, tak mám radost :)